# O(n^2)
# class Solution(object):
#     def trap(self, height):
#         """
#         :type height: List[int]
#         :rtype: int
#         """
#         statistics = height.copy()
#         statistics.sort()
#         length = len(height)
#         last_height = 0
#         index = 0
#         total = 0
#         while index < length:
#             if statistics[index] <= last_height:
#                 index += 1
#             else:
#                 now_height = statistics[index]
#                 for i in range(length):
#                     if height[i] >= now_height:
#                         left_index = i
#                         break
#                 for i in range(length):
#                     if height[i] >= now_height:
#                         left_index = i
#                         break
#                 for i in range(length):
#                     if height[length - 1 - i] >= now_height:
#                         right_index = length - 1 - i
#                         break
#                 if right_index <= left_index + 1:
#                     break
#                 else:
#                     count = 0
#                     for i in range(left_index + 1, right_index):
#                         if height[i] < now_height:
#                             count += 1
#                     total += count * (now_height - last_height)
#                     index += 1
#                     last_height = now_height
#         return total

class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        interval = []
        total = 0
        left_index = 0
        right_index = 0
        length = len(height)
        for i in range(length):
            if height[i] > 0:
                left_index = i
                max_value = height[i]
                right_index = left_index + 1
                break
        if right_index == left_index:
            return 0
        else:
            while right_index < length:
                if height[right_index] >= max_value:
                    max_value = height[right_index]
                    if right_index - left_index >= 2:
                        interval.append([left_index, right_index])
                    left_index = right_index
                right_index += 1
            left_max = left_index
            left_index = 0
            right_index = 0
            for i in range(0, length - 1 - left_max):
                if height[length - 1 - i] > 0:
                    right_index = length - 1 - i
                    max_value = height[length - 1 - i]
                    left_index = right_index - 1
                    break
            if left_index != right_index:
                while left_index >= left_max:
                    if height[left_index] >= max_value:
                        max_value = height[left_index]
                        if right_index - left_index >= 2:
                            interval.append([left_index, right_index])
                        right_index = left_index
                    left_index -= 1
            for item in interval:
                upper_limit = min(height[item[0]], height[item[1]])
                for i in range(item[0] + 1, item[1]):
                    total += upper_limit - height[i]
            return total

data = Solution()
height = [0,0,0,2,0,8,6,7,7]
print(data.trap(height))